package org.example.day;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/24 21:01
 */
public class Solution_trapping_rain_water {

    public static void main(String[] args) {
        System.out.println(new Solution_trapping_rain_water().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

    public int trap(int[] height) {
        int ans = 0;

        int[] left_max = new int[height.length];
        int[] right_max = new int[height.length];

        left_max[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            left_max[i] = Math.max(left_max[i-1], height[i]);
        }

        right_max[height.length - 1] = height[height.length - 1];
        for (int i = height.length-2; i >= 0; i--) {
            right_max[i] = Math.max(right_max[i+1], height[i]);
        }

        for (int i = 0; i < height.length; i++) {
            ans += Math.max(Math.min(left_max[i], right_max[i]) - height[i], 0);
        }

        return ans;
    }
}
